public class Main {

    // 选择排序
    public static void selectSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 数组为空或只有一个元素，无需排序
        }

        int n = array.length;
        // 遍历所有元素，最后一个元素会自然有序
        for (int i = 0; i < n - 1; i++) {
            // 寻找[i, n-1]区间内的最小值索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            // 将找到的最小值与第i个位置的元素交换
            if (minIndex != i) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }

    // 堆排序
    public static void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 数组为空或只有一个元素，无需排序
        }

        int n = array.length;

        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        // 从最后一个元素开始，逐个提取最大值并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶（最大值）与末尾元素交换
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // 对剩余元素重新构建大顶堆
            heapify(array, i, 0);
        }
    }

    // 堆调整函数，维护大顶堆性质
    private static void heapify(int[] array, int n, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 如果左子节点大于根节点
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }

        // 如果右子节点大于当前最大值
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点，则交换并递归调整
        if (largest != i) {
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;

            // 递归调整受影响的子树
            heapify(array, n, largest);
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 数组为空或只有一个元素，无需排序
        }

        int n = array.length;
        boolean swapped;

        // 外层循环控制需要进行多少轮比较
        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            // 内层循环进行每一轮的比较和交换
            // 每轮结束后，最大的元素会"浮"到数组末尾
            for (int j = 0; j < n - 1 - i; j++) {
                // 如果当前元素大于下一个元素，则交换它们
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }

            // 如果在这一轮中没有发生交换，说明数组已经有序，可以提前退出
            if (!swapped) {
                break;
            }
        }
    }

    // 快速排序入口方法
    public static void quickSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 数组为空或只有一个元素，无需排序
        }
        quickSort(array, 0, array.length - 1);
    }

    // 快速排序递归实现
    private static void quickSort(int[] array, int left, int right) {
        if (left < right) {
            // 分区操作，返回基准元素的最终位置
            int pivotIndex = partition(array, left, right);

            // 递归排序基准元素左侧的子数组
            quickSort(array, left, pivotIndex - 1);
            // 递归排序基准元素右侧的子数组
            quickSort(array, pivotIndex + 1, right);
        }
    }

    // 分区操作，选择最右侧元素作为基准
    private static int partition(int[] array, int left, int right) {
        int pivot = array[right]; // 选择最右侧元素作为基准
        int i = left - 1; // i指向小于基准元素区域的最后一个位置

        // 遍历数组，将小于基准的元素放到左侧，大于基准的元素放到右侧
        for (int j = left; j < right; j++) {
            if (array[j] <= pivot) {
                i++;
                // 交换元素
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // 将基准元素放到它的最终位置
        int temp = array[i + 1];
        array[i + 1] = array[right];
        array[right] = temp;

        return i + 1; // 返回基准元素的索引
    }

    class Solution {
        public int[] sortArray(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return nums;
            }

            int n = nums.length;

            // 构建大顶堆
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(nums, n, i);
            }

            // 逐个提取最大元素并调整堆
            for (int i = n - 1; i > 0; i--) {
                // 将当前堆顶（最大值）与末尾元素交换
                int temp = nums[0];
                nums[0] = nums[i];
                nums[i] = temp;

                // 对剩余元素重新构建大顶堆
                heapify(nums, i, 0);
            }

            return nums;
        }

        // 堆调整函数，维护大顶堆性质
        private void heapify(int[] arr, int n, int i) {
            // 初始化最大值位置为当前节点
            int largest = i;
            // 左子节点索引
            int left = 2 * i + 1;
            // 右子节点索引
            int right = 2 * i + 2;

            // 如果左子节点大于当前最大值，更新最大值位置
            if (left < n && arr[left] > arr[largest]) {
                largest = left;
            }

            // 如果右子节点大于当前最大值，更新最大值位置
            if (right < n && arr[right] > arr[largest]) {
                largest = right;
            }

            // 如果最大值不是当前节点，需要交换并递归调整
            if (largest != i) {
                int temp = arr[i];
                arr[i] = arr[largest];
                arr[largest] = temp;

                // 递归调整受影响的子树
                heapify(arr, n, largest);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}